package greedy;

import java.util.Arrays;

/**
 * @ Author     ：侯耀祖
 * @ Description：
 */
public class largestSumAfterKNegations {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int min = 0;
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 0){
                max = i;
            }
            if (nums[i] > 0){
                min = i;
                break;
            }
        }
        int temp = -nums[max] > nums[min] ? min : max;
        for (int i = 0; k > 0; i++) {
            if (i == nums.length-1){
                i -= 1;
            }
            if (nums[i] < 0){
                nums[i] = -nums[i];
            } else if (nums[i] == 0){
                break;
            } else {
                nums[temp] = -nums[temp];
            }
            k--;
        }
        return Arrays.stream(nums).sum();
    }
}
